package leetcode_core.leetcode_1;

import org.junit.Test;

public class MinInsertions {
    public int minInsertions(String s) {
        //1.定义dp数组,是一个二维的数组dp[i][j]:s[i...j]变成回文串所需要的最小次数
        int[][] dp = new int[s.length()+5][s.length()+5];
        //2.写出base-case
        //当i=j的时候,指针指向一个字符,这时候的本身就是一个回文串,不需要插入,等于0
        for(int i = 0;i<s.length();i++){
            dp[i][i] = 0;
        }
        //3.写状态转移
        //回文类型的状态转移不是传统的顺序遍历方式
        //遍历方式如何来确定呢?
        //我们来观察DP-table,dp-table被初始化为具有斜对角0的表
        //那么我们行就应当从倒数第二行开始
        //也就是i = n-2的地方开始
        //j的话我们根据回文串的特点,它要扩散,那么我们就让它向后走一格,直到s.length()-1为止就好了
        for(int i = s.length()-2;i>=0;i--){
            for(int j = i+1;j<s.length();j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i][j-1],dp[i+1][j])+1;//最多是2,最少是1,因为都不是回文串
                }
            }
        }
        return dp[0][s.length()-1];
    }

    @Test
    public void test(){
        System.out.println(minInsertions("zzazz"));
        System.out.println(minInsertions("mbadm"));
        System.out.println(minInsertions("leetcode"));
    }
}
